<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4249：Walls 防壁</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Walls 防壁</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Walls 防壁</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Walls 防壁                </h1>
                <p>时间限制：30s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>
<div>你入手了一款JOI社发售的游戏。你对这款游戏十分上手，每天玩得不亦乐乎。</div>
<div>某一天，玩家之中出现了一个叫做&ldquo;镭射&rdquo;的关卡。这个关卡十分的难，连老司机玩家也只有很低的概率才能通过。正在三番五次挑战这个关卡的你，很快判断出通过的可能性是存在的，并考虑写一个程序来计算出对策。</div>
<div>镭射关卡在一个配置有N个防壁的地形上进行。地形为长方形，分成了一些1*1的正方形区域。每个区域可以用两个非负整数(x,y)表示，左下角的区域为(0,0),(x,y)表示(0,0)往右数x个区域，再往上数y个区域的位置。</div>
<div>关卡开始后，敌人会出现并顺次进行M轮攻击。第i次攻击时，敌人将会从区域(Pi,N+1)向区域(Pi,0)进行直线镭射射击。</div>
<div>每个防壁放在y坐标相同的一些连续的区域中。防壁i(1&lt;=i&lt;=N)是左右长度为Bi-Ai+1，上下宽度为1的长方形，初始位置为(Ai,i)到(Bi,i)的所有区域。在敌人开始攻击之前以及两次攻击的间隙，你可以任意次地左右移动防壁。一次移动可以让防壁向右移动一个区域，或者向左移动一个区域。</div>
<div>镭射在穿过一个防壁后威力会减少。现在为了将镭射的威力最小化，需要移动防壁使得镭射能穿过所有的防壁。你想让移动防壁的次数尽量少。</div>
<div>现在给出关卡开始时每个防壁的位置，以及每个敌人的攻击位置，为了让每一发镭射都穿过所有的防壁，请你输出每个防壁移动次数的最小值。</div>
</div>
<p></p></p><hr/><h3>输入格式</h3><p><p>&nbsp;第一行两个空格分隔的整数N,M，表示这个关卡有N个防壁，敌人将会进行M轮攻击。</p>
<div>接下来N行，第i行(1&lt;=i&lt;=N)有两个空格分隔的整数Ai,Bi，表示关卡开始时防壁i被放置在(Ai,i)到(Bi,i)的所有区域的位置上。</div>
<div>接下来M行，第i行有一个整数Pi，表示第i次攻击时，敌人从(Pi,N+1)向(Pi,0)进行直线镭射射击。</div></p><hr/><h3>输出格式</h3><p><p>&nbsp;输出N行，第i行表示防壁i的移动次数的最小值。</p></p><hr/><h3>样例输入</h3><pre>4 4
0 3
4 4
2 7
8 11
6
4
3
8
</pre><hr/><h3>样例输出</h3><pre>5
10
1
7</pre><hr/><h3>提示</h3><p><div>1&lt;=N&lt;=2*10^5</div>
<div>1&lt;=M&lt;=2*10^5</div>
<div>0&lt;=Ai&lt;=Bi&lt;=10^9 (1&lt;=i&lt;=N)</div>
<div>0&lt;=Pi&lt;=10^9 (1&lt;=i&lt;=M)</div></p><hr/><h3>题目来源</h3><p>JOI 2014~2015 春季training合宿 竞技4 By POPOQQQ
</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4249" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4249" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>